package leetcode;

import java.util.ArrayList;
import java.util.List;

public class Code38 {
    public static void main(String[] args) {
        System.out.println(new Code38().countAndSay(5));
    }
    static public String countAndSay(int n) {
        if (n==1){
            return "1";
        }else{
            return createNow(countAndSay(n-1));
        }
    }

    private static String createNow(String countAndSay) {
        char before = countAndSay.charAt(0);
        int index = 0;
        StringBuilder builder = new StringBuilder();
        for (int a=0;a<countAndSay.length();a++){
            if(before==countAndSay.charAt(a)){
                index++;
            }else{
                builder.append(index);
                builder.append(before);
                before=countAndSay.charAt(a);
                index=1;
            }
        }
        builder.append(index);
        builder.append(before);
        return builder.toString();
    }

    public String countAndSay2(int n) {
        List<List<Integer>> item = new ArrayList<>(35);
        for (int a = 0; a < n; a++) {
            if (a == 0) {
                List<Integer> list = new ArrayList<>();
                list.add(1);
                item.add(list);
            } else {
                List<Integer> before = item.get(a - 1);
                List<Integer> nowItem = new ArrayList<>();
                int index = before.get(0);
                int size = 0;
                for (int b = 0; b < before.size(); b++) {
                    if (before.get(b) == index) {
                        size++;
                    } else {
                        nowItem.add(size);
                        nowItem.add(index);
                        size = 1;
                        index = before.get(b);
                    }
                }
                nowItem.add(size);
                nowItem.add(index);
                item.add(nowItem);
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int a = 0; a < item.get(n - 1).size(); a++) {
            stringBuilder.append(item.get(n - 1).get(a));
        }
        return stringBuilder.toString();
    }
}
